package com.wz.leetcode.linkedlist;

public class ReverseList2_92 {
    public ListNode reverseBetween(ListNode head, int left, int right) {
        if (head == null || head.next == null || left <= 0 || right == 0 || left >= right) {
            return head;
        }

        ListNode dummy = new ListNode(-1, head);
        // 找到这段反转链表的前驱prev
        int i = 1;
        ListNode cur = dummy;
        while (i <= left - 1 && cur != null) {
            cur = cur.next;
            i++;
        }
        ListNode prev = cur;
        // 找到这段反转链表的末尾
        ListNode t = cur.next;
        // 反转该链表
        cur = cur.next;
        // 最终p是这段反转链表的开头
        ListNode p = prev;
        // 这段反转链表的下一个
        ListNode next = null;
        while (i <= right && cur != null) {
            next = cur.next;
            cur.next = p;
            p = cur;
            cur = next;
            i++;
        }
        // 修正中间段
        prev.next = p;
        t.next = next;
        return dummy.next;
    }
}
